/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:最大子序和.java
 * Date:2021/02/18 14:21:18
 */

package org.bytedance.动态和贪心;

/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 */
public class 最大子序和 {

    public static void main(String[] args) {
        最大子序和 instance = new 最大子序和();

        int[] input1 = new int[]{
                -2, 1, -3, 4, -1, 2, 1, -5, 4
        };
        int i = instance.maxSubseqSum(input1);
        System.out.println(i);

        input1 = new int[]{
                1
        };
        i = instance.maxSubseqSum(input1);
        System.out.println(i);


        input1 = new int[]{0};
        i = instance.maxSubseqSum(input1);
        System.out.println(i);

        input1 = new int[]{-1};
        i = instance.maxSubseqSum(input1);
        System.out.println(i);

        input1 = new int[]{-10000};
        i = instance.maxSubseqSum(input1);
        System.out.println(i);

    }

    public int maxSubseqSum(int[] nums) {
        if (nums == null) throw new IllegalArgumentException("bad param");
        if (nums.length == 1) return nums[0];
        int res = Integer.MIN_VALUE;
        int length = nums.length;
        int[] dp = new int[length];
        dp[0] = nums[0];
        for (int i = 1; i < length; i++) {
            dp[i] = (dp[i - 1] + nums[i]) < nums[i] ? nums[i] : (dp[i - 1] + nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }


}
